Free Solved Question Paper of BCS42 - Introduction to Algorithm Design for June 2023

1. (a) What is complexity of algorithm? Explain space complexity and time complexity of algorithms with the help of example. (5 marks)

Answer :

Algorithm complexity refers to the amount of computational resources that an algorithm requires. The two main types of complexity are time complexity and space complexity.

Time Complexity: This measures the amount of time an algorithm takes to complete as a function of the length of the input. It is commonly expressed using Big O notation. For example, a linear search algorithm has a time complexity of $O(n)$, meaning that in the worst case, it takes time proportional to the number of elements in the input list.

Space Complexity: This measures the amount of memory space an algorithm needs to run to completion. For instance, consider an algorithm that processes an array and requires an additional array of the same size to store the results. If the input array has $n$ elements, the space complexity would be $O(n)$.

Example:

Consider a simple algorithm that finds the maximum element in an array of integers:

function findMax(arr):
    max = arr[0]
    for i = 1 to length(arr)-1:
        if arr[i] > max:
            max = arr[i]
    return max

For this algorithm:

• → Time Complexity: $O(n)$, as it must check each element of the array once.
• → Space Complexity: $O(1)$, since it only uses a fixed amount of extra space regardless of the input size.

1. (b) Write linear search algorithm and do analysis of this algorithm for best case and worst case. (5 marks)

Answer :

The linear search algorithm iterates through each element in a list to find a target value. Here is the linear search algorithm:

function linearSearch(arr, target):
    for i = 0 to length(arr)-1:
        if arr[i] == target:
            return i
    return -1

For this algorithm:

• → Best Case: The best-case scenario occurs when the target value is at the first position of the array. In this case, the algorithm will find the target in the first comparison, resulting in a time complexity of $O(1)$.
• → Worst Case: The worst-case scenario occurs when the target value is at the last position of the array or not present in the array. In this case, the algorithm will compare each element in the array, resulting in a time complexity of $O(n)$.

1. (c) Using mathematical induction method, show that for all positive integers (n): $\sum_{i=1}^n i^2 = \frac{n(n+1)(2n+1)}{6}$ (5 marks)

Answer :

To prove the statement $\sum_{i=1}^n i^2 = \frac{n(n+1)(2n+1)}{6}$ for all positive integers (n), we will use mathematical induction.

Base Case:

For (n = 1):
$\sum_{i=1}^1 i^2 = 1^2 = 1$
and
$\frac{1(1+1)(2 \cdot 1 + 1)}{6} = \frac{1 \cdot 2 \cdot 3}{6} = 1$
Thus, the base case holds true since $\sum_{i=1}^1 i^2 = 1$ and $\frac{1(1+1)(2 \cdot 1 + 1)}{6} = 1$.

Induction Hypothesis:

Assume the formula holds for some positive integer (k), i.e.,
$\sum_{i=1}^k i^2 = \frac{k(k+1)(2k+1)}{6}$

Induction Step:

We need to show that the formula holds for (k + 1), i.e.,
$\sum_{i=1}^{k+1} i^2 = \frac{(k+1)(k+2)(2(k+1)+1)}{6}$

Starting with the left-hand side, we can write:
$\sum_{i=1}^{k+1} i^2 = \sum_{i=1}^k i^2 + (k+1)^2$

Using the induction hypothesis, we substitute $\sum_{i=1}^k i^2$:
$\sum_{i=1}^{k+1} i^2 = \frac{k(k+1)(2k+1)}{6} + (k+1)^2$

Factor out $(k+1)$ from both terms:
$\sum_{i=1}^{k+1} i^2 = \frac{k(k+1)(2k+1)}{6} + \frac{6(k+1)^2}{6}$
$= \frac{(k+1)[k(2k+1) + 6(k+1)]}{6}$
$= \frac{(k+1)[2k^2 + k + 6k + 6]}{6}$
$= \frac{(k+1)(2k^2 + 7k + 6)}{6}$
$= \frac{(k+1)(k+2)(2k+3)}{6}$

This completes the induction step, and hence by mathematical induction, the formula $\sum_{i=1}^n i^2 = \frac{n(n+1)(2n+1)}{6}$ holds for all positive integers (n).

1. (d) What is Adjacency matrix? Write adjacency matrix for the following graph: (5 marks)

Answer :

An adjacency matrix is a square matrix used to represent a finite graph. The elements of the matrix indicate whether pairs of vertices are adjacent or not in the graph. In the matrix, a value of 1 indicates that there is an edge between the vertices, and a value of 0 indicates that there is no edge.

The adjacency matrix for the given graph is:

   A  B  C  D  E  F
A  0  1  0  0  1  0
B  1  0  1  0  0  0
C  0  1  0  1  0  0
D  0  0  1  0  1  0
E  1  0  0  1  0  1
F  0  0  0  0  1  0

2. (a) Write Depth-First Search (DFS) algorithm. Also traverse the following graph using DFS from node A. (7 marks)

Answer :

Depth-First Search (DFS) Algorithm:

→ Initialize an empty stack and push the starting node (A) onto the stack.
→ Initialize an empty set to keep track of visited nodes.
→ While the stack is not empty:
    → Pop the top node from the stack.
    → If the node has not been visited:
        → Mark it as visited and add it to the visited set.
        → Push all adjacent nodes that have not been visited onto the stack.

DFS Traversal of the given graph from node A:

Traversal Steps:
→ Start at A, visit A.
→ Push nodes D and B (adjacent to A) onto the stack.
→ Pop B from the stack, visit B.
→ Push nodes E and C (adjacent to B) onto the stack.
→ Pop C from the stack, visit C.
→ Push node F (adjacent to C) onto the stack.
→ Pop F from the stack, visit F.
→ Pop E from the stack, visit E.
→ Push node D (adjacent to E) onto the stack.
→ Pop D from the stack, visit D.

DFS Traversal Order:
A, B, C, F, E, D

2. (b) Solve the following recurrence relation using recurrence tree method: $T(n) = 4T(\frac{n}{2}) + n$ (3 marks)

Answer :

3. (a) Write Kruskal’s algorithm for finding Minimum Cost Spanning Tree (MCST). Find MCST of the following graph using Kruskal’s algorithm. (8 marks)

Answer :

Kruskal’s Algorithm for finding Minimum Cost Spanning Tree (MCST):

→ Sort all the edges in non-decreasing order of their weight.
→ Initialize an empty forest (a set of trees), where each vertex in the graph is a separate tree.
→ Create a set to keep track of the edges included in the MCST.
→ For each edge in the sorted list:
    → If the edge connects two different trees, add it to the set of edges included in the MCST and merge the two trees into a single tree.
→ Repeat until there are (V-1) edges in the MCST, where V is the number of vertices.

Step 1: Sort all edges in non-decreasing order of weight:
→ (D, E) - 2
→ (E, F) - 3
→ (A, B) - 3
→ (A, D) - 4
→ (B, E) - 4
→ (C, F) - 4
→ (A, E) - 5
→ (B, C) - 8

Step 2: Initialize forest:
→ Forest: {A}, {B}, {C}, {D}, {E}, {F}

Step 3: Add edges to the forest, ensuring no cycles are formed:
→ Add (D, E) - 2
    Forest: {A}, {B}, {C}, {D, E}, {F}
→ Add (E, F) - 3
    Forest: {A}, {B}, {C}, {D, E, F}
→ Add (A, B) - 3
    Forest: {A, B}, {C}, {D, E, F}
→ Add (A, D) - 4
    Forest: {A, B, D, E, F}, {C}
→ Add (C, F) - 4
    Forest: {A, B, C, D, E, F}

Step 4: Minimum Cost Spanning Tree (MCST):
→ Edges included in MCST:
    (D, E) - 2
    (E, F) - 3
    (A, B) - 3
    (A, D) - 4
    (C, F) - 4

Total cost of MCST: 2 + 3 + 3 + 4 + 4 = 16

3. (b) Explain use of Big oh (O) notation in the analysis of algorithms with example. (2 marks)

Answer :

Big O Notation:

Big O notation is used in computer science to describe the performance or complexity of an algorithm. Specifically, it characterizes functions according to their growth rates: how the runtime or space requirements of an algorithm grow relative to the input size. It provides an upper bound on the growth rate of the function, allowing us to understand the worst-case scenario for algorithm performance.

Example:

Consider the algorithm for finding the maximum element in an array of size $n$:

Algorithm FindMax(arr)
    max = arr[0]
    for i = 1 to length(arr) - 1
        if arr[i] > max
            max = arr[i]
    return max

In this example, the algorithm makes a single pass through the array, comparing each element to the current maximum.
The number of comparisons is directly proportional to the size of the array, $n$.
Therefore, the time complexity of this algorithm is O(n), which means that in the worst-case scenario, the time it takes to complete the task increases linearly with the input size.

4. (a) Find the optimal solution to the knapsack (fractional) problem for n = 5 and m = 10, where n is the number of objects and m is the capacity of the knapsack. Profit and Weight of each object are given below: (6 marks)
$(P_1, P_2, P_3, P_4, P_5) = (10, 30, 35, 20, 40)$
$(W_1, W_2, W_3, W_4, W_5) = (3, 5, 2, 6, 11)$

Answer :

Solution:

To solve the fractional knapsack problem, we follow these steps:

→ Calculate the profit-to-weight ratio for each object.
→ Sort the objects in non-increasing order of their profit-to-weight ratio.
→ Add objects to the knapsack starting from the highest ratio until the knapsack is full or we run out of objects.

Step 1: Calculate the profit-to-weight ratio:

$P/W_1 = 10/3 \approx 3.33$
$P/W_2 = 30/5 = 6$
$P/W_3 = 35/2 = 17.5$
$P/W_4 = 20/6 \approx 3.33$
$P/W_5 = 40/11 \approx 3.64$

Step 2: Sort the objects by profit-to-weight ratio:

1. Object 3: $17.5$
2. Object 2: $6$
3. Object 5: $3.64$
4. Object 1: $3.33$
5. Object 4: $3.33$

Step 3: Add objects to the knapsack:

→ Add Object 3 (Weight = 2, Profit = 35). Remaining capacity = 10 - 2 = 8.
→ Add Object 2 (Weight = 5, Profit = 30). Remaining capacity = 8 - 5 = 3.
→ Add Object 5 partially (Weight = 3, Profit = 3/11 * 40 ≈ 10.91). Remaining capacity = 3 - 3 = 0.

Total profit: $35 + 30 + 10.91 = 75.91$

Therefore, the optimal solution to the fractional knapsack problem is a total profit of 75.91.

4. (b) In context of algorithm study, explain the following with the help of an example of each: (4 marks)

1. Upper Bound
2. Backtracking

Answer :

1. Upper Bound:

In the analysis of algorithms, the upper bound is a limit that defines the worst-case scenario for the running time or space requirements of an algorithm. It gives the maximum time an algorithm can take to complete or the maximum space it can occupy, as a function of the input size. The upper bound is typically expressed using Big O notation.

Example:

Consider the Bubble Sort algorithm. Bubble Sort repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. The process is repeated until the list is sorted.

Algorithm BubbleSort(arr)
    n = length(arr)
    for i = 0 to n-1
        for j = 0 to n-i-2
            if arr[j] > arr[j+1]
                swap(arr[j], arr[j+1])

In the worst case, Bubble Sort requires $O(n^2)$ comparisons and swaps, where $n$ is the number of elements in the list. Therefore, the upper bound of the Bubble Sort algorithm is O(n^2).

2. Backtracking:

Backtracking is a general algorithmic technique for solving problems incrementally, building candidates for the solutions, and abandoning candidates (backtracking) as soon as it is determined that the candidate cannot lead to a valid solution. This approach is used for solving combinatorial problems such as puzzles, games, and constraint satisfaction problems.

Example:

Consider the problem of solving a Sudoku puzzle. Sudoku is a 9x9 grid where some cells are pre-filled with numbers. The goal is to fill the empty cells so that each row, each column, and each 3x3 subgrid contains the numbers 1 to 9 without repeating.

Algorithm SolveSudoku(grid)
    if no empty cell
        return true
    for each number from 1 to 9
        if number is valid in the empty cell
            place number in the cell
            if SolveSudoku(grid) is true
                return true
            remove number from cell
    return false

In this example, the algorithm tries to place a number in an empty cell and recursively attempts to solve the rest of the puzzle. If placing a number leads to a solution, the algorithm returns true. If not, it removes the number (backtracks) and tries the next possible number. This continues until the puzzle is solved or all possibilities are exhausted.

5. (a) Sort the following list using Bubble sort algorithm. Show the steps of sorting: (6 marks)
$30, 8, 7, 14, 20, 28, 10$

Answer :

Bubble Sort Algorithm:

Bubble Sort is a simple sorting algorithm that repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. The pass through the list is repeated until the list is sorted.

Steps of Sorting:

Initial list: $30, 8, 7, 14, 20, 28, 10$

Pass 1:

→ Compare 30 and 8, swap: $8, 30, 7, 14, 20, 28, 10$
→ Compare 30 and 7, swap: $8, 7, 30, 14, 20, 28, 10$
→ Compare 30 and 14, swap: $8, 7, 14, 30, 20, 28, 10$
→ Compare 30 and 20, swap: $8, 7, 14, 20, 30, 28, 10$
→ Compare 30 and 28, swap: $8, 7, 14, 20, 28, 30, 10$
→ Compare 30 and 10, swap: $8, 7, 14, 20, 28, 10, 30$

Pass 2:

→ Compare 8 and 7, swap: $7, 8, 14, 20, 28, 10, 30$
→ Compare 8 and 14, no swap: $7, 8, 14, 20, 28, 10, 30$
→ Compare 14 and 20, no swap: $7, 8, 14, 20, 28, 10, 30$
→ Compare 20 and 28, no swap: $7, 8, 14, 20, 28, 10, 30$
→ Compare 28 and 10, swap: $7, 8, 14, 20, 10, 28, 30$

Pass 3:

→ Compare 7 and 8, no swap: $7, 8, 14, 20, 10, 28, 30$
→ Compare 8 and 14, no swap: $7, 8, 14, 20, 10, 28, 30$
→ Compare 14 and 20, no swap: $7, 8, 14, 20, 10, 28, 30$
→ Compare 20 and 10, swap: $7, 8, 14, 10, 20, 28, 30$

Pass 4:

→ Compare 7 and 8, no swap: $7, 8, 14, 10, 20, 28, 30$
→ Compare 8 and 14, no swap: $7, 8, 14, 10, 20, 28, 30$
→ Compare 14 and 10, swap: $7, 8, 10, 14, 20, 28, 30$

Pass 5:

→ Compare 7 and 8, no swap: $7, 8, 10, 14, 20, 28, 30$
→ Compare 8 and 10, no swap: $7, 8, 10, 14, 20, 28, 30$

Pass 6:

→ Compare 7 and 8, no swap: $7, 8, 10, 14, 20, 28, 30$

Final sorted list: $7, 8, 10, 14, 20, 28, 30$

5. (b) Write algorithm for adding two matrices of order $m \times n$ and find its time complexity. (4 marks)

Answer :

Algorithm for Adding Two Matrices:

Given two matrices, $A$ and $B$, each of order $m \times n$, the algorithm for adding these matrices can be described as follows:

Algorithm AddMatrices(A, B)
    Input: Two matrices A and B of order m x n
    Output: Matrix C which is the sum of A and B
    
    for i = 0 to m-1
        for j = 0 to n-1
            C[i][j] = A[i][j] + B[i][j]
    return C

Explanation:

→ The algorithm iterates over each element of the matrices using two nested loops.
→ For each element, it computes the sum of the corresponding elements from matrices $A$ and $B$ and stores it in matrix $C$.
→ Finally, the resulting matrix $C$ is returned.

Time Complexity:

The time complexity of the algorithm can be analyzed as follows:

→ The outer loop runs $m$ times.
→ For each iteration of the outer loop, the inner loop runs $n$ times.
→ Therefore, the total number of iterations is $m \times n$.

Thus, the time complexity of the algorithm is $O(m \times n)$.